# -*- coding: utf-8 -*-

"""5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成"""

class Solution:
    """
    这道题原来是遍历所有中心点，对每个中心点，同步向左右扩展，既然题出在动态规划里面，就看看用相关算法来解。
    考虑这个场景，当计算完前 p 个字符，当后移到 p+1 个字符的时候，如果是要加入前面的回文串，会怎么做？
    定义前面的p个字符中最尾的一个回文串片段是 [left, right, flag] ( 当flag = 1 时，表示这是一个单个字符重复回文串 )，
        当 [left-1] == [right+1]即[p+1]时，这个回文串会扩展 2 个字符, c + aba + c，回文中心没有转移；
        当 [left:right] 全部相同，且 [left] == [p+1], 也就是重复字符串和第 p+1 个相同，扩展 1 个字符，会组成如 aaaaa + a 的重复字符回文串，回文中心转移了。

        否则 [left-1] ≠ [right+1]即[p+1]时，这个回文串回将被冻结，不会成为前 p+1 个字符中的尾部回文串；

        -------------------------------------------------------------
        最后专门关于 [p+1, p+1] 自身单字符是否应该以 flag = 1 的形式加入尾部回文集合中？
        如果当前状态有重复串，且已经扩展了这1个字符，那么就不应该在单独构造一个单字符重复回文串。如果当前状态没有能扩展这个字符的重复回文串，就要单独构造1个单字符回文串。

    所以，对前p个字符，其尾部回文串应该是多个，定义tail集合。如果需要展示所有的回文串，可以再定义一个frozen集合，用来保存后续不能用来扩展的回文串。

    以上算法也是直接用的递推状态来做的动态规划，没有先写出递归运算。

    ---------------------------------------------------------------------------------------------------------------------------------------------------------
    虽然上面这个解法在提交后的时间空间占用上还是让我满意，但是看到题解上的动态规划过程还是觉得他的解法更直观。
    定义 f(i,j) 为计算 [i:j] 片段是否是回文字符串。
    递归定义：
        f(i,j) = f(i+1, j-1) AND (s[i] == s[j])
    递归基础：
        最内侧，要么是单个字符，要么是相邻的两个字符
        f(i,i) = true
        f(i,i+1) = s[i] == s[j]
    本身是想学习一下他这个递推的状态转换过程，从递归计算来看，还是需要从递归基础（每个单字符，每个相邻字符处）多点开花，铺展开来。让我对递归递推的视野更广阔了。
    """
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s

        tail, freeze = [[0, 0, 1]], []

        longest, longestPalin = 0, ''
        p = 1
        while p < len(s):
            # print([(s[t[0]: t[1]+1], t[2]) for t in tail])
            temp, has_add_p = [], False
            for palin in tail:
                left, right, flag = palin[0], palin[1], palin[2]
                if flag == 1 and s[right] == s[p]:
                    temp.append([left, p, 1])
                    has_add_p = True
                elif left > 0:
                    if s[left-1] == s[p]:
                        temp.append([left-1, p, 0])
                    elif right-left > 0:
                        freeze.append(palin)
            if not has_add_p:
                temp.append([p, p, 1])

            for palin in temp:
                left, right = palin[0], palin[1]
                if right-left+1 > longest:
                    longest, longestPalin = right-left+1, s[left: right+1]

            tail = temp
            p += 1

        return longestPalin

if __name__ == '__main__':
    print(Solution().longestPalindrome('cbbd'))
